//
// Description: 5779. 装包裹的最小浪费空间
// Created by Loading on 2021/6/6.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int minWastedSpace(vector<int> &packages, vector<vector<int>> &boxes) {
    constexpr int MOD = 1e9 + 7;
    //package空间求和
    /* 使用 accumulate 方法出现 int 越界，init 需要设置为 0LL，不可设置为 0 */
//    LL packages_sums = accumulate(packages.begin(), packages.end(), 0LL);
    LL packages_sums = 0;
    for (auto &x : packages) {
        packages_sums += x;
    }
    //排序
    sort(packages.begin(), packages.end());
    for (auto &v : boxes) {
        sort(v.begin(), v.end());
    }

    LL res = LLONG_MAX;
    //遍历所有供应商
    for (auto &box : boxes) {
        //存在装不下的包裹
        if (packages.back() > box.back()) {
            continue;
        }
        //上次遍历到的包裹的位置索引
        int index = 0;
        //总空间
        LL sum = 0;
        for (auto &x : box) {
            //遍历供应商的箱子，找到第一个空间大于当前箱子的包裹
            auto pos = upper_bound(packages.begin(), packages.end(), x) - packages.begin();
            //上次遍历到 index，一共有 pos - index 个包裹需要使用当前箱子
            sum += (pos - index) * x;
            //更新索引
            index = pos;
        }
        //计算浪费的空间
        LL diff = sum - packages_sums;
        //取最小的浪费
        /* 注意：千万不可在比较的时候对 diff 取模，因为取模以后值可能会变小，导致取最小浪费的结果错误 */
        res = min(res, diff);
    }

    if (res == LLONG_MAX) {
        return -1;
    }
    /* 返回的时候再进行取模运算 */
    return (int) (res % MOD);
}

int main() {
    vector<int> packages = {2, 3, 5};
    vector<vector<int>> boxes = {{4, 8},
                                 {2, 8}};

    cout << minWastedSpace(packages, boxes) << endl;
}